//
// Description: 437. 路径总和 III
// Created by Loading on 2022/7/30.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

int pathSum(TreeNode *root, int targetSum) {
    if (!root) {
        return 0;
    }
    /* 注意要使用long，递归途中可能出现爆int */
    function<int(TreeNode *, long)> dfs = [&](TreeNode *node, long sum) {
        if (!node) {
            return 0;
        }

        int res = 0;
        if (sum == node->val) {
            ++res;
        }
        // 左右子树分别递归
        res += dfs(node->left, sum - node->val);
        res += dfs(node->right, sum - node->val);

        return res;
    };

    int res = dfs(root, targetSum);
    // 左右子树分别作为根节点开始遍历
    res += pathSum(root->left, targetSum);
    res += pathSum(root->right, targetSum);

    return res;
}

int main() {
    vector<int> nums{1, -1, 2, -1, -1, -1, 3};
    auto root = generateTreeNode(nums);
    int targetSum = 3;

    int res = pathSum(root, targetSum);

    cout << res << endl;

    return 0;
}